/**
*   time:11-8-13 18:10
*   Code practice from C++ primer P546
*   Data structure: Queue
*   for learning template using
*/
#include<iostream>


//declaration that Queue is a template needed for friend declaration in QueueItem
template <class Type>class Queue;
//function template declaration must precede friend declaration in QueueItem
template <class T>
std::ostream& operator<<(std::ostream&, const Queue<T>&);

template <class Type>class QueueItem
{
    friend class Queue<Type>;
    //needs access to item and next
    friend std::ostream&
    operator<< <Type>(std::ostream&, const Queue<Type>&);
    //private class: no public section
    QueueItem(const Type &t):item(t),next(0){}
    Type item;              //value stored in this element
    QueueItem *next;        //pointer to next element in Queue
};

template <class Type>class Queue
{
    //needs access to head
    friend std::ostream& operator<< <Type>(std::ostream&, const Queue<Type>&);
    public:
    //empty Queue
    Queue():head(0),tail(0){}
    //construct a Queue from a pair of iterators on some sequence
    template <class It>
    Queue(It beg,It end):head(0),tail(0){copy_elems(beg,end);}
    //copy control to manage pointers to QueueItems in the Queue
    Queue(const Queue &Q):head(0),tail(0){copy_elems(Q);}
    Queue& operator=(const Queue&);
    ~Queue() {destroy();}
    //replace current Queue by contents delimited by a pair of iterators
    template <class Iter> void assign(Iter, Iter);
    //return element from head of Queue
    //unchected operation:front on an empty Queue is undefined
    Type& front() {return head->item;}
    const Type &front()const {return head->item;}
    void push(const Type&);     //add element to back of Queue
    void pop();                 //remove element from head of Queue
    bool empty()const           //true if no elements in the Queue
    {
        return head==0;
    }
    private:
    QueueItem<Type> *head;  //pointer to the first element in Queue
    QueueItem<Type> *tail;  //pointer to the last element in Queue
    //utility functions used by copy constructor,assignment,and destructor
    void destroy();         //delete all the elements
    void copy_elems(const Queue&);//copy elements from parameter
    //version of copy to be used by assign to copy elements from iterator range
    template <class Iter> void copy_elems(Iter,Iter);
};

template<class Type> void Queue<Type>::destroy()
{
    while(!empty())
        pop();
}

template<class Type> void Queue<Type>::pop()
{
    //pop is unchecked:Popping off an empty Queue is undefined
    QueueItem<Type> *p=head;    //keep pointer to head so we can delete it
    head=head->next;            //head new points to next element
    delete(p);                   //delete old head element
}

template<class Type> void Queue<Type>::push(const Type &val)
{
    //allocate a new QueueItem object
    QueueItem<Type> *pt=new QueueItem<Type>(val);
    //put item onto existing queue
    if(empty())
        head=tail=pt;       //the Queue has one element only
    else
    {
        tail->next=pt;      //add new element to end of Queue
        tail=pt;
    }
}

template<class Type> void Queue<Type>::copy_elems(const Queue &orig)
{
    //copy elements from orig into this Queue
    //loop stops when pt==0, which happens when we reach orig.tail
    for(QueueItem<Type> *pt=orig.head;pt;pt=pt->next)
        push(pt->item);     //copy the element
}

template<class Type>
std::ostream& operator<<(std::ostream &os,const Queue<Type> &q)
{
    os<<"<";
    QueueItem<Type> *p;
    for(p=q.head;p;p=p->next)
        os<<p->item<<" ";
    os<<">";
    return os;
}

template <class T> template <class Iter>
void Queue<T>::assign(Iter beg,Iter end)
{
    destroy();
    copy_elems(beg,end);
}

template <class Type> template <class It>
void Queue<Type>::copy_elems(It beg, It end)
{
    while(beg!=end)
    {
        push(*beg);
        ++beg;
    }
}

template <class Type>
Queue<Type>& Queue<Type>::operator=(const Queue &orig)
{
    destroy();
    copy_elems(orig);
    return this;
}

int main()
{
    Queue<int> qi;
    qi.push(1);
    qi.push(2);
    qi.push(3);
    qi.push(4);
    qi.push(5);
    qi.push(6);
    qi.push(7);
    std::cout<<qi<<std::endl;

    Queue<int> qi2=qi;
    std::cout<<qi2<<std::endl;
}
